#include <vector>

using namespace std;

class Solution
{
public:
    // 思路： 二分查找
    //   数组可以分为两个区间，左边区间的值都大于右边区间的值
    // 第一个区间： nums[left] <= nums[mid] && nums[mid] > nums[right]
    int findMin(vector<int> &nums)
    {
        int left = 0;
        int right = nums.size() - 1;
        int mid = 0;
        while (left <= right)
        {
            mid = left + (right - left) / 2;
            if (nums[left] <= nums[mid] && nums[mid] <= nums[right]) // 左   中  右 是升序排列的，整个区间有序了
            {                                                        // 第二个区间
                return nums[left];
            } 
            else if (nums[mid] >= nums[left]) // 为什么是num[mid] >= nums[left] 就是第一个区间？
            {                                 // 第一个区间
                left = mid + 1;
            }
            else if (nums[mid] <= nums[right]) // 中间到右边是单调递增的（第二段有序）
            {
                right = mid;
            }
        }
        return -1;
    }
};